Transmitting a real-time data stream simultaneously to multiple receivers over unreliable networks (e.g. wireless multicast) in a timely and reliable manner is a challenging problem because different receivers experience different packet losses and therefore request for different packets to be retransmitted. In the case of unicast sessions, reliable data delivery is often implemented by means of positive acknowledgments (ACK) after each transmitted packet and some form of Automatic Repeat reQuest (ARQ) mechanism. If an ACK does not arrive within a certain time interval, the sender considers that the packet was lost by the receiver and initiates its retransmission. In multicast scenarios, where data must be transmitted simultaneously to several receivers, traditional ARQ aimed at satisfying individual requests from each receiver becomes inefficient. The reason is that while a packet is retransmitted to a specific receiver, all receivers that do not need that particular retransmission stay idle for a time period, which makes it impossible to meet stringent real-time constraints. Moreover, the use of ACKs to ensure reliable data delivery in the case of multicast with feedback is not straightforward, since the sender must wait for the ACKs of each receiver before transmitting any data. This implies additional delays in data delivery and requires receiver coordination, particular if the receivers are sharing a common feedback channel. Case in point, the IEEE 802.11 standard foresees that multicast data be transmitted in open-loop fashion, i.e. without any feedback mechanism. This makes it impossible to provide real-time guarantees for applications such as live video streaming or industrial control.
Others have presented solutions in which the transmitter is given the ability to code across packets. Fountain Codes, which present a throughput optimal solution to multicast over packet erasure channels, have been extended to cope with unequal error protection and real-time requirements. One solution for video streaming uses unequal error protection in a block-based coding scheme to increase the probability of delivering certain frames that are more important than others. Another solution uses a sliding coding window, such that the transmitter sends the oldest packet in the window and a recovery coded transmission before the coding window moves forward.
Network coding allows the transmitter and intermediate nodes to perform algebraic operations on a set of packets, thereby generating linear combinations of packets that are sent to the receivers. In feedback based online network coding, the linear combinations of packets are functions of notifications sent by the receivers over one or more feedback channels. In the COPE protocol, intermediate nodes satisfy the requests of several receivers simultaneously by combining packets from different flows. For the case when all packets are to be delivered to all receivers there exist coding schemes capable of producing linear combinations that can be immediately decodable by a large number of receivers. Likewise, solutions exist to ensure that receivers with poorer channel conditions can still decode at least some of the packets. It has been shown that minimizing the number of packets that miss their deadlines in the case of multicast with stringent end-to-end delay is NP-hard.
However, the present embodiments enable the transmitter to offer real-time guarantees by prioritizing the packets in the transmit queue as a function of the packet deadlines and the available (possibly partial) feedback from the receivers, thereby producing linear combinations that allow the receivers to decode the right packet at the right time, i.e. before the packet deadline has passed. The presently disclosed coding module is able to make coding decisions in the presence of incomplete feedback information, including sending uncoded packets whenever necessary. It is further able to maximize the number of receivers that can decode a given packet immediately upon reception of a sent linear combination.